package pers.qianyu.month_202012.date_20201225.dp_bag;

/**
 * 92. 背包问题
 * https://www.lintcode.com/problem/backpack/description
 * <strong>01背包最值为题</strong>
 *
 * @author mizzle rain
 * @date 2020-12-25 14:42
 */
public class BackPack {
    /**
     * @param m:       An integer m denotes the size of a backpack
     * @param weights: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] weights) {
        int[] dp = new int[m + 1];
        for (int weight : weights) {
            for (int size = m; size >= weight; size--) {
                dp[size] = Math.max(dp[size], dp[size - weight] + weight);
            }
            //ArrayUtil.printArrayAsMarkdownTable(weight, dp);
        }
        return dp[m];
    }

    public static void main(String[] args) {
        int result = new BackPack().backPack(10, new int[]{3, 4, 5, 8});
        System.out.println("result = " + result);
    }
}
